#include <iostream>
using std::cout;
using std::endl;

// 第一个等于的
int FindFirst(int arr[], int size, int data) {
  int low = 0, high = size - 1;
  int idx = -1;
  while (low <= high) {
    int mid = low + (high - low) / 2;  // 防止溢出
    if (arr[mid] == data) {
      idx = mid;
      high = mid - 1;  // 继续往前走
    } else if (arr[mid] > data) {
      high = mid - 1;
    } else {
      low = mid + 1;
    }
  }
  return idx;
}
void TestFindFirst() {
  int arr[] = {1, 1, 2, 3, 3, 3, 4, 4, 5, 5};
  int idx = FindFirst(arr, sizeof(arr) / sizeof(int), 3);
  cout << "FindFirst, idx:" << idx << endl;
}

// 最后一个等于的
int FindLast(int arr[], int size, int data) {
  int low = 0, high = size - 1;
  int idx = -1;
  while (low <= high) {
    int mid = low + ((high - low) >> 1);  // 移位效率更高（>>优先级比+-低）
    if (arr[mid] == data) {
      idx = mid;
      low = mid + 1;  // 继续往后走
    } else if (arr[mid] > data) {
      high = mid - 1;
    } else {
      low = mid + 1;
    }
  }
  return idx;
}
void TestFindLast() {
  int arr[] = {1, 1, 2, 3, 3, 3, 4, 4, 5, 5};
  int idx = FindLast(arr, sizeof(arr) / sizeof(int), 3);
  cout << "FindLast, idx:" << idx << endl;
}

// 第一个大于等于的
int FindFirstBigEqu(int arr[], int size, int data) {
  int low = 0, high = size - 1;
  int idx = -1;
  while (low <= high) {
    int mid = low + (high - low) / 2;
    if (arr[mid] >= data) {
      idx = mid;
      high = mid - 1;  // 继续往前走
    } else {
      low = mid + 1;
    }
  }
  return idx;
}
void TestFindFirstBigEqu() {
  int arr[] = {1, 1, 3, 3, 3, 5, 5};
  int idx = FindFirstBigEqu(arr, sizeof(arr) / sizeof(int), 4);
  cout << "FindFirstBigEqu, idx:" << idx << endl;
}

// 最后一个小于等于的
int FindLastSmallEqu(int arr[], int size, int data) {
  int low = 0, high = size - 1;
  int idx = -1;
  while (low <= high) {
    int mid = low + ((high - low) >> 1);
    if (arr[mid] <= data) {
      idx = mid;
      low = mid + 1;  // 继续往后走
    } else {
      high = mid - 1;
    }
  }
  return idx;
}
void TestFindLastSmallEqu() {
  int arr[] = {1, 1, 3, 3, 3, 5, 5};
  int idx = FindLastSmallEqu(arr, sizeof(arr) / sizeof(int), 3);
  cout << "FindLastSmallEqu, idx:" << idx << endl;
}

int main() {
  TestFindFirst();
  TestFindLast();
  TestFindFirstBigEqu();
  TestFindLastSmallEqu();
}